package Leetcode;

import base.ListNode;

/**
 * 给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表。
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 */
public class 力扣92_反转链表II {
    public static void main(String[] args) {
        ListNode a1 = new ListNode(1);
        ListNode a2 = new ListNode(2);
        ListNode a3 = new ListNode(3);
        ListNode a4 = new ListNode(4);
        ListNode a5 = new ListNode(5);
        a1.next = a2;
        a2.next = a3;
        a3.next = a4;
        a4.next = a5;

        ListNode listNode = reverseBetween(a1, 2, 4);
        System.out.println(listNode);
    }

    /**
     * 第一种方式
     */
    static ListNode reverseBetween(ListNode head, int left, int right) {
        // 辅助节点
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode endNext = null;
        int idx = 1;
        while (cur != null) {
            if (idx < left) {
                pre = cur;
            }
            if (idx == right) {
                if (cur.next != null) {
                    endNext = cur.next;
                    cur.next = null;
                }
                break;
            }
            cur = cur.next;
            idx++;
        }

        // 反转
        ListNode reverse = reverse(pre.next);

        // 将反转后的链表重新接入原来链表
        pre.next.next = endNext;
        pre.next = reverse;
        // while (reverse != null) {
        //     if (reverse.next == null) {
        //         reverse.next = endNext;
        //         break;
        //     }
        //     reverse = reverse.next;
        // }

        // 返回节点
        return dummy.next;
    }

    static ListNode reverse(ListNode node) {
        ListNode cur = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = cur;
            cur = node;
            node = next;
        }
        return cur;
    }


    /**
     * 第二种方式
     */
    static ListNode reverseBetween2(ListNode head, int left, int right) {
        if (left >= right) {
            return head;
        }
        // 辅助节点
        ListNode top = new ListNode();
        top.next = head;
        // 寻找要反转左右节点
        ListNode leftNodePre = null, leftNode = null;
        ListNode rightNode = null, rightNodeNext = null;
        ListNode cur = top;
        for (int i = 0; i <= right; i++) {
            if (i + 1 == left) {
                leftNodePre = cur;
                leftNode = cur.next;
            }
            if (i == right) {
                rightNode = cur;
                rightNodeNext = cur.next;
            }
            cur = cur.next;
        }
        // 反转
        reverse2(leftNode, rightNode);
        // 将反转后的链表重新接入原来链表
        leftNodePre.next = rightNode;
        leftNode.next = rightNodeNext;
        // 返回节点
        return top.next;
    }

    static void reverse2(ListNode head, ListNode end) {
        ListNode next = null;
        while (head != end) {
            ListNode curNext = head.next;
            head.next = next;
            next = head;
            head = curNext;
        }
        head.next = next;
    }

}
